1. Field of the Invention
The present invention relates in general to a network switch port for storing incoming packets as sequences of cells in a cell memory until they can be forwarded, and in particular to a system for determining when to discard incoming cells as the number of cells stored in the cell memory approaches its maximum cell storage capacity.
2. Description of Related Art
A typical network switch for routing data transmissions (packets) between network buses includes a set of input switch ports for receiving packets arriving on the network buses, a set of output switch ports for forwarding packets outward on the network buses, and a switch fabric for routing packets between the input and output switch ports. Each input switch port includes a memory for storing packets arriving on a network until the switch fabric can forward them to an output switch port. Each output switch port may also include a memory for storing packets it receives via the switch fabric until the port can forward them outward on a network bus.
Since many networks transmit packets of variable size, some switch ports organize their memories into a set blocks, with each block being sufficiently large to hold the largest possible packet. However when many packets are much smaller than the maximum size, much of the storage capacity of most memory blocks is wasted. To make more efficient use of memory space, some input switch ports include a protocol processor for converting the incoming packet into a sequence of relatively small cells of uniform size. Each memory blocks is sized just large enough to hold a single cell. Such a switch port also includes a traffic manager for writing each cell of the sequence in a separate memory block cell and for reads reading the cells derived from a packet out of the cell memory and forwarding them onward to an output switch port via the switch fabric. The output switch port's traffic manager receives and stores cell sequence arriving from the switch fabric and later forwards it to another protocol processor which reassembles the cell sequence into a packet and forwards its outward on a network bus. By converting variable sized packets to sequences of uniformly sized cells, the network switch makes more efficient use of the data storage capacity of the input and output port memories because most memory blocks are completely filled with data.
Some network systems assign each packet to one of a set of “flows”. For example packets originating from a particular source and directed to the same destination may be assigned to the same packet flow. The network may accord each flow with a particular class of service, and a flow's class of service affects the manner in which the network forwards packets assigned to that flow. For example a flow's class of service may determine the maximum and minimum rates at which a network switch may forward packets assigned to that flow, the priority with which the network switch forward packets of that flow relative to packets of other flows, and the amount of cell memory space that can be used for holding cells derived from packets assigned to that flow. Such network systems typically include a “flow identification number” (FIN) identifying packet's flow. The input switch port that converts a packet into a cell sequence incorporate the packet's FIN into each cell derived from the packet. When a traffic manager receives a cell it can read its FIN value and use it as a key into a database defining the cell's class of service. This enables the traffic manger to determine how to treat each cell packet for example with respect to forwarding rates and priority.
When a traffic manager is unable to forward cells as fast as it receives and stores them, its cell memory can fill up, and be unable to store any more incoming cells. Thus when a cell memory is full or is approaching full, it is necessary for the traffic manager to begin discarding incoming cells. One way to do that is to simply discard all cells of any packet arriving at a time when the cell memory is too full to hold all of the cells of the packet. However since in many network systems it is desirable to treat some packets with a higher forwarding priority than others, a port that simply waits until its cell memory is too full to accept a next incoming packet treats all packets with the same discard priority.
Some network switch ports allocate separate portions of cell memory space to various flows or groups of flows. Thus when a traffic manager receives an incoming cell sequence, it determines the amount of memory space assigned to the cells' flow and discards the incoming cell sequence, if cells of that flow are already occupying their maximum allotted space in cell memory. Such a system can provide some flows with a measure of priority over others with respect to discard operations by the manner in which it allocates memory space to various flows. For example high priority, low volume flows can be permitted to occupy all available cell memory space so that packets of such flows are never discarded if there is any available cell memory space. With lower priority flows being assigned to more limited portions of the cell memory space, they are more likely to be discarded.
While it is desirable to discard packets assigned to lower priority flows more frequently than packets assigned to higher priority flows, it is also desirable to discard packets assigned to flows of similar priority at similar rates. Suppose a traffic manager allocates a portion of its cell memory to a group of flows, all of which have the same priority. If the traffic manager waits until the cell memory space allocated to a group of flows is full or nearly full and then discards each incoming packets assigned to that group of flows when it is too large to be stored in any remaining unused portion of the allocated memory space, the discard burden is likely to be unevenly distributed among those flows. For example a flow that happens to include a burst of packets arriving at a switch port immediately after its allocated cell memory space is temporarily filled will bear all of the discard burden while packets of another flow arriving shortly thereafter when cell memory space happens to become available will bear none of the discard burden.
Some traffic managers employ a “random early discard” system to reduce the likelihood of such inequalities in discard burden distribution among flows. In a random early discard systems, the traffic manager not only allocates a maximum cell memory space to group of flows, it also establishes a threshold level below that maximum. When the number of cells in the cell memory is above the threshold level, but below the maximum level, the traffic manager discards some, but not all of the arriving packets assigned to those flows, with the decision as to whether to discard each incoming packet being made randomly or pseudo-randomly. Thus not all of the discard burden falls on packets arriving after the allocated cell memory space is completely filled; some of the burden falls on packets arriving before the allocated memory space is completely filled.
When flows of differing priority are allocated the same portion of memory space, each flow can be assigned a separate discard weight. The higher a flow's discard weight, the less likely that the traffic manger will discard packets assigned to that flow when the traffic manager is operating in a random early discard mode. Typically the traffic manager will randomly generate a number whenever a packet arrives, compare the random number to the packet's discard weight, and discard the packet if the random number exceeds the packet's discard weight.
One drawback to a random early discard system is that it may cause a traffic manager to unnecessarily discard packets. For example when a burst of incoming cells temporarily drives the number of stored cells above the random early discard threshold, the traffic manager begins discarding cells, even though the burst would not otherwise fill the allocated memory space to is maximum level. As long as the number of stored cells remains above the random early discard threshold level, the traffic manager will continue to unnecessarily randomly discard cells even when the rate at which cells arriving at the traffic manager falls to a level no greater than the rate at which the traffic manager is currently sending cells out of the cell memory. What is needed is a weighted random early discard system for a network switch that reduces the likelihood that packets will be unnecessarily discarded.